The coding of information words (of a length generally denoted K) into code words (of a length generally denoted N, with N>K) is used when it is required to add redundancy to the information concerned in order to retrieve the entirety of the original information even if a part thereof is erroneous or lost, as in the case of the transmission of information in a channel suffering interference or the storage thereof on a medium subject to deterioration (such as scratches on an optical disk).
The decoding carried out on reception (or on reading in the case of storage) in order to retrieve the original information words generally comprises a first phase of correcting errors, which consists in retrieving precisely the code word sent (or stored) from the word received (vocabulary also utilized to designate the word read in the case of storage), despite any errors and thanks to the redundancy introduced, and then a“demapping” phase that consists in carrying out the inverse operation to that effected on coding.
In this context, there are known low-density parity check codes, referred to hereinafter as LDPC codes, as described for example in the paper “Low density parity check codes”, by R. Gallager in IEEE Trans. Inform. Theory, vol. IT-8, pp. 21-28, 1962.
These codes are particularly interesting not only because they are very close to the capacity of the channel (Shannon limit) and they offer the best possible compromise between yield and performance (close to the Gilbert-Varshamov limit), but also because they allow message passing type iterative decoding.
Two main algorithms for decoding LDPC codes have been proposed before now, whether these are binary codes (for which the symbols representing the information are 0 or 1, i.e. taken in the Galois field GF(2)) or non-binary codes (for which the symbols are taken in the Galois field GF(q) with q>2).
The first, proposed in the paper cited above under the name “probabilistic decoding” is generally known (and denoted hereinafter) as SPA (“Sum-Product Algorithm”) or BP (“Belief Propagation”) decoding. This algorithm is generally qualified as optimal because SPA decoding converges toward the maximum likelihood on condition that the bipartite graph associated with the LDPC code does not contain cycles. In the case of non-binary LDPC codes, this algorithm is unusable in a real communication system, however, because of its very wide dynamic, which leads to high instability of the calculations effected. Moreover, it necessitates the production of a large number of products, which makes it complex, and it is dependent on the knowledge of the thermal noise.
The second, sub-optimal, decoding algorithm is primarily known by the name MSA (“Min-Sum Algorithm”). It is less complex than the SPA and independent of the knowledge of the thermal noise, but it suffers a loss of performance, in terms of the binary error rate, compared to the SPA that generally varies from 0.25 dB to 1 dB for an AWGN (“Additive White Gaussian Noise”) channel, as a function of the yield, the irregularity or the length of the code used.